/*
    求最大和的子串
    有几种方法，一种是递归求解，复杂度O(lgN)。
    另外一种是O(n)的扫描方法
*/

#include <iostream>
#define LEN 5
#define MINUS 0x80000000
#define MAX(a,b,c)  a>b ? (a>c?a:c)   \
                        : (b>c?b:c)
using namespace std;


//思想比较简单，但是maxEndsHere的溢出问题考虑起来有点头痛
//怎样让它能处理全部是负数的情况，而又不出现负溢出呢？
//如果把maxEndsHere设成是负无穷的话，加上一个负数就会溢出，所以设成0
//并且把maxSoFar设成负无穷。 这样即使是负数也比maxSoFar要大。
void MSA_1(int a[], int len)  //扫描法
{
    int maxSoFar = MINUS;   //在此之前的最大和  **这个设成负无穷
    int maxEndsHere = 0;    //以此元素为最后一个元素的最大子串和  **这个设成0
    for (int i=0; i<len; i++)
    {
        if (maxEndsHere + a[i] > a[i])
        {
            maxEndsHere += a[i];
        }
        else
        {
            maxEndsHere = a[i];
        }
        if (maxEndsHere > maxSoFar)
        {
            maxSoFar = maxEndsHere;
        }
    }
    cout<<"MSA_1:"<<maxSoFar<<endl;
}


//方法二是用递归去求。每次把一个串分为左右两边，两边的最大子串都求出来之后，
//再求一下分别以左边的最右端元素为结尾的最大子串，和右边的最左端元素为开始的最大子串，这两个子串是可以连接起来求和的。
//这样，最后得到了3个子串，取其中最大者，如果有相等的，就任意取一个。
int recur_func(int *left, int *right)
{
    if (left > right)
    {
        return MINUS;
    } else if (left == right)
    {
        return *left;
    }
    //
    int *mid = left + int((right-left)/2);  //奇怪，这里如果写成 (left+right)/2 就会出错
    int maxLeftRegion = recur_func(left, mid);
    int maxRightRegion = recur_func(mid+1, right);

    int temp=0;
    int maxWithRightBorder = MINUS; //这两个是表示，可以连接到一起的，左右两边的最大子串
    int maxWidthLeftBorder = MINUS;
    for (int *i=mid+1; i<=right; i++)
    {
        temp += *i;
        if (temp > maxWidthLeftBorder)
        {
            maxWidthLeftBorder = temp;
        }
    }
    temp = 0;
    for (int *i=mid; i>=left; i--)
    {
        temp += *i;
        if (temp > maxWithRightBorder)
        {
            maxWithRightBorder = temp;
        }
    }
    return MAX(maxLeftRegion, maxRightRegion, maxWidthLeftBorder+maxWithRightBorder);
}

void MSA_2(int a[], int len)
{
    int maxSum = MINUS;
    if (len < 1)
    {
        return;
    }
    else if (len == 1)      // left == right == mid
    {
        maxSum = a[0];
    }
    else
    {
        maxSum = recur_func(a, &a[len-1]);
    }
    cout<<"MSA_2:"<<maxSum<<endl;
}


int main()
{
    int a[LEN] = {-10,30,-3,10,-5};
    MSA_1(a, LEN);
    MSA_2(a, LEN);
}
